Computer systems typically comprise a combination of computer programs and hardware, such as semiconductors, transistors, chips, circuit boards, storage devices, and processors. The storage devices store data and the computer programs, which are executed by the processors.
The computer programs are often divided into pieces, which call or invoke each other. The pieces are typically referred to as methods, functions, modules, parts, classes, procedures, or subroutines. When a first method (the caller) calls or invokes a second method (the callee), the caller method stops executing and the callee method gains control of the processor and begins executing. When the callee method stops executing, it returns control of the processor to the caller method, which resumes execution at the next instruction following the call instruction that invoked the callee method.
In order to facilitate this call and return technique, computers often use a call stack, which is also known as a run-time stack, a function stack, an execution stack, an invocation stack, or simply a stack. The call stack comprises entries (also known as frames) for each active method. An entry stores information about the execution of its respective method. The information may comprise any, some, or all of identifiers of the method, the return address of the method (the location of the instruction in the caller method to execute next after the callee method returns), the values of local variables read or written by the method, parameters passed to the method, an evaluation stack of operands for arithmetic or logical operations, a pointer to the current instance of the method, the enclosing method context, and/or the privilege or authority level of the method.
The call stacks use the principle of Last In First Out (LIFO), meaning that the last (or most recent) entry added (pushed) to the top of the call stack is the first (or next) item that is removed (popped) from the top of the call stack. For example, in response to a first method invoking a second method, a new entry is created for the first method and pushed to the top of the call stack. If the second method calls a third method, a new entry for the second method is pushed onto the call stack. Once a currently executing method ends, the entry of its caller method is popped from the top of the stack and used to restore the operating environment of the caller method. Since many methods may call each other and calls may be nested or even recursive, the call stack grows and shrinks as the program executes.